home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / progutil / stdwin.zoo / tools / glob.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-30  |  10.3 KB  |  587 lines
  1. /* This software is copyright (c) 1986 by Stichting Mathematisch Centrum.
  2.  * You may use, modify and copy it, provided this notice is present in all
  3.  * copies, modified or unmodified, and provided you don't make money for it.
  4.  *
  5.  * Written 86-jun-28 by Guido van Rossum, CWI, Amsterdam <guido@mcvax.uucp>
  6.  */
  7.  
  8. /*
  9.  * 'Glob' routine -- match *, ? and [...] in filenames.
  10.  * Extra services: initial ~username is replaced by username's home dir,
  11.  * initial ~ is replaced by $HOME, initial $var is replaced by
  12.  * return value of getenv("var").
  13.  * Quoting convention: \ followed by a magic character inhibits its
  14.  * special meaning.
  15.  * Nonexisting $var is treated as empty string; nonexisting ~user
  16.  * is copied literally.
  17.  */
  18.  
  19. #include <stdio.h>
  20. #include <strings.h>
  21. #include <ctype.h>
  22. #include <pwd.h>
  23. #include <sys/types.h>
  24. #ifdef atarist
  25. #include <dirent.h>
  26. #include <stddef.h>
  27. #include <stdlib.h>
  28. #include <memory.h>
  29. #include <unixlib.h>
  30. #else
  31. #include <sys/dir.h>
  32. #endif
  33.  
  34.  
  35. struct passwd *getpwnam();
  36. char *getenv();
  37.  
  38. #ifdef __STDC__
  39. void *malloc(size_t);
  40. void *realloc(void *, size_t);
  41. #else
  42. char *malloc();
  43. char *realloc();
  44. #endif
  45.  
  46. #define EOS '\0'
  47. #define SEP '/'    /* atari users please note: this is ok, gcc lib will translate */
  48. #define DOT '.'
  49. #define QUOTE '\\'
  50.  
  51. #define BOOL int
  52. #define NO 0
  53. #define YES 1
  54.  
  55. #ifdef atarist
  56. #define MAXPATH 128
  57. #else
  58. #define MAXPATH 1024
  59. #endif
  60. #define MAXBASE 256
  61.  
  62. #define META(c) ((char)((c)|0200))
  63. #define M_ALL META('*')
  64. #define M_ONE META('?')
  65. #define M_SET META('[')
  66. #define M_RNG META('-')
  67. #define M_END META(']')
  68.  
  69. struct flist {
  70.     int len;
  71.     char **item;
  72. };
  73.  
  74. #ifdef __STDC__
  75. # define    P(s) s
  76. #else
  77. # define P(s) ()
  78. #endif
  79.  
  80. static char *makestr P((char *start , char *end ));
  81. static char *addstr P((char *dest , char *src , char *end ));
  82. static void formpath P((char *dest , char *head , char *tail , unsigned int size ));
  83. static char *gethome P((char *username ));
  84. static int compare P((char **p , char **q ));
  85. static void addfile P((struct flist *list , char *head , char *tail ));
  86. static void clear P((struct flist *list ));
  87. static void discard P((struct flist *list ));
  88. static BOOL match P((char *name , char *pat ));
  89. static void segment P((struct flist *files , char *mid , char *pat ));
  90. static void findfiles P((struct flist *files , char *tail ));
  91. static void glob1 P((char *pat , struct flist *files ));
  92. #undef P
  93.  
  94. /* Make a null-terminated string of the chars between two pointers */
  95. /* (Limited length, static buffer returned) */
  96.  
  97. static char *
  98. makestr(start, end)
  99.     char *start;
  100.     char *end;
  101. {
  102.     static char buf[100];
  103.     char *p= buf;
  104.     
  105.     while (start < end && p < &buf[100])
  106.         *p++ = *start++;
  107.     *p= EOS;
  108.     return buf;
  109. }
  110.  
  111. /* Append string to buffer, return new end of buffer.  Guarded. */
  112.  
  113. static char *
  114. addstr(dest, src, end)
  115.     char *dest;
  116.     char *src;
  117.     char *end;
  118. {
  119.     while (*dest++ = *src++) {
  120.         if (dest >= end)
  121.             break;
  122.     }
  123.     return --dest;
  124. }
  125.  
  126. /* Form a pathname by concatenating head, maybe a / and tail. */
  127. /* Truncates to space available. */
  128.  
  129. static void
  130. formpath(dest, head, tail, size)
  131.     char *dest;
  132.     char *head;
  133.     char *tail;
  134.     unsigned int size; /* sizeof dest */
  135. {
  136.     char *start= dest;
  137.     
  138.     for (;;) {
  139.         if (--size == 0)
  140.             goto out;
  141.         if ((*dest++ = *head++) == EOS)
  142.             break;
  143.     }
  144.     if (*tail != EOS && size != 0) {
  145.         --dest;
  146.         ++size;
  147.         if (dest > start && dest[-1] != SEP) {
  148.             *dest++ = SEP;
  149.             --size;
  150.         }
  151.         for (;;) {
  152.             if (--size == 0)
  153.                 goto out;
  154.             if ((*dest++ = *tail++) == EOS)
  155.                 break;
  156.         }
  157.     }
  158.     return;
  159.     
  160.  out:    *dest= EOS;
  161. }
  162.  
  163. /* Find a user's home directory, NULL if not found */
  164.  
  165. static char *
  166. gethome(username)
  167.     char *username;
  168. {
  169.     struct passwd *p;
  170.     
  171.     p= getpwnam(username);
  172.     if (p == NULL)
  173.         return NULL;
  174.     return p->pw_dir;
  175. }
  176.  
  177. /* String compare for qsort */
  178.  
  179. static int
  180. compare(p, q)
  181.     char **p;
  182.     char **q;
  183. {
  184.     return strcmp(*p, *q);
  185. }
  186.  
  187. /*
  188.  * Maintain lists of strings.
  189.  * When memory is full, data is lost but 
  190.  */
  191.  
  192. static void
  193. addfile(list, head, tail)
  194.     struct flist *list;
  195.     char *head;
  196.     char *tail;
  197. {
  198.     char *str;
  199.     
  200.     str= malloc((size_t) strlen(head) + strlen(tail) + 2);
  201.     
  202.     if (str == NULL)
  203.         return;
  204.     if (list->item == 0) {
  205.         list->len= 0;
  206.         list->item= (char**) malloc((size_t)sizeof(char*));
  207.     }
  208.     else {
  209.         list->item= (char**) realloc((char*)list->item,
  210.                 (size_t) (list->len+1)*sizeof(char*));
  211.         if (list->item == 0)
  212.             list->len= 0;
  213.     }
  214.     if (list->item != NULL) {
  215.         formpath(str, head, tail, MAXPATH);
  216.         list->item[list->len++]= str;
  217.     }
  218.     else
  219.         free(str);
  220. }
  221.  
  222. /* Clear the fields of a struct flist before first use */
  223.  
  224. static void
  225. clear(list)
  226.     struct flist *list;
  227. {
  228.     list->len= 0;
  229.     list->item= NULL;
  230. }
  231.  
  232. /* Free memory held by struct flist after use */
  233.  
  234. static void
  235. discard(list)
  236.     struct flist *list;
  237. {
  238.     int i= list->len;
  239.     
  240.     if (list->item != NULL) {
  241.         while (--i >= 0) {
  242.             if (list->item[i] != NULL)
  243.                 free(list->item[i]);
  244.         }
  245.         free((char*)list->item);
  246.         list->item= NULL;
  247.     }
  248.     list->len= 0;
  249. }
  250.  
  251. /* Pattern matching function for filenames */
  252. /* Each occurrence of the * pattern causes a recursion level */
  253.  
  254. static BOOL
  255. match(name, pat)
  256.     char *name;
  257.     char *pat;
  258. {
  259.     char c, k;
  260.     BOOL ok;
  261.     
  262.     while ((c= *pat++) != EOS) {
  263.         switch (c) {
  264.  
  265.         case M_ONE:
  266.             if (*name++ == EOS)
  267.                 return NO;
  268.             break;
  269.  
  270.         case M_ALL:
  271.             if (*pat == EOS)
  272.                 return YES;
  273.             for (; *name != EOS; ++name) {
  274.                 if (match(name, pat))
  275.                     return YES;
  276.             }
  277.             return NO;
  278.  
  279.         case M_SET:
  280.             ok= NO;
  281.             k= *name++;
  282.             while ((c= *pat++) != M_END) {
  283.                 if (*pat == M_RNG) {
  284.                     if (c <= k && k <= pat[1])
  285.                         ok= YES;
  286.                     pat += 2;
  287.                 }
  288.                 else if (c == k)
  289.                     ok= YES;
  290.             }
  291.             if (!ok)
  292.                 return NO;
  293.             break;
  294.  
  295.         default:
  296.             if (*name++ != c)
  297.                 return NO;
  298.             break;
  299.  
  300.         }
  301.     }
  302.     return *name == EOS;
  303. }
  304.  
  305. /* Perform pattern matching for one segment of the pathname */
  306.  
  307. static void
  308. segment(files, mid, pat)
  309.     struct flist *files;
  310.     char *mid;
  311.     char *pat;
  312. {
  313.     char path[MAXPATH];
  314.     int i;
  315.     DIR *dirp;
  316. #ifdef atarist
  317.     struct dirent *dp;
  318. #else
  319.     struct direct *dp;
  320. #endif
  321.     struct flist new;
  322.     
  323.     clear(&new);
  324.     for (i= 0; i < files->len; ++i) {
  325.         strcpy(path, files->item[i]);
  326.         strcat(path, mid);
  327.         free(files->item[i]);
  328.         files->item[i]= NULL;
  329.         dirp= opendir(path);
  330.         if (dirp == NULL)
  331.             continue;
  332.         while ((dp= readdir(dirp)) != NULL) {
  333.             if (*dp->d_name == DOT && *pat != DOT)
  334.                 ; /* No meta-match on initial '.' */
  335.             else if (match(dp->d_name, pat))
  336.                 addfile(&new, path, dp->d_name);
  337.         }
  338.         closedir(dirp);
  339.     }
  340.     discard(files);
  341.     *files= new;
  342. }
  343.  
  344. /* Finish by matching the rest of the pattern (which has no metas) */
  345.  
  346. static void
  347. findfiles(files, tail)
  348.     struct flist *files;
  349.     char *tail;
  350. {
  351.     int i;
  352.     struct flist new;
  353.     char path[MAXPATH];
  354.  
  355.     if (*tail == EOS || files->len == 0)
  356.         return;
  357.     clear(&new);
  358.     for (i= 0; i < files->len; ++i) {
  359.         strcpy(path, files->item[i]);
  360.         strcat(path, tail);
  361.         free(files->item[i]);
  362.         files->item[i]= NULL;
  363.         if (access(path, 0) == 0)
  364.             addfile(&new, path, "");
  365.     }
  366.     discard(files);
  367.     *files= new;
  368. }
  369.  
  370. static void
  371. glob1(pat, files)
  372.     char *pat;
  373.     struct flist *files;
  374. {
  375.     char mid[MAXPATH];
  376.     char *end= mid;
  377.     char *basestart= mid;
  378.     BOOL meta= NO;
  379.     char c;
  380.     
  381.     clear(files);
  382.     addfile(files, "", "");
  383.     for (;;) {
  384.         switch (c= *pat++) {
  385.  
  386.         case EOS:
  387.         case SEP:
  388.             *end= EOS;
  389.             if (meta) {
  390.                 if (basestart == mid)
  391.                     segment(files, "", basestart);
  392.                 else if (basestart == mid+1) {
  393.                     static char sepstr[]= {SEP, EOS};
  394.                     segment(files, sepstr, basestart);
  395.                 }
  396.                 else {
  397.                     basestart[-1]= EOS;
  398.                     segment(files, mid, basestart);
  399.                 }
  400.                 if (files->len == 0)
  401.                     return;
  402.                 end= basestart= mid;
  403.                 meta= NO;
  404.             }
  405.             else if (c == EOS)
  406.                 findfiles(files, mid);
  407.             if (c == EOS)
  408.                 return;
  409.             *end++= c;
  410.             basestart= end;
  411.             break;
  412.  
  413.         case M_ALL:
  414.         case M_ONE:
  415.         case M_SET:
  416.             meta= YES;
  417.             /* Fall through */
  418.         default:
  419.             *end++ = c;
  420.  
  421.         }
  422.     }
  423. }
  424.  
  425. /*
  426.  * The main 'glob' routine: does $ and ~ substitution and \ quoting,
  427.  * and then calls 'glob1' to do the pattern matching.
  428.  * Returns 0 if file not found, number of matches otherwise.
  429.  * The matches found are appended to the buffer, separated by
  430.  * EOS characters.  If no matches were found, the pattern is copied
  431.  * to the buffer after $ and ~ substitution and \ quoting.
  432.  */
  433.  
  434. int
  435. glob(pat, buf, size)
  436.     char *pat;
  437.     char *buf;
  438.     unsigned int size; /* sizeof buf */
  439. {
  440.     char *p, *q;
  441.     char c;
  442.     struct flist files;
  443.     char *start= buf;
  444.     char *end= buf+size;
  445.     
  446.     c= *pat;
  447.     if (c == '~') {
  448.         p= ++pat;
  449.         while (*p != EOS && *p != SEP)
  450.             ++p;
  451.         if (p == pat) {
  452.             q= getenv("HOME");
  453.             if (q == NULL)
  454.                 --pat;
  455.             else
  456.                 buf= addstr(buf, q, end);
  457.         }
  458.         else {
  459.             q= gethome(makestr(pat, p));
  460.             if (q == NULL)
  461.                 --pat;
  462.             else {
  463.                 buf= addstr(buf, q, end);
  464.                 pat= p;
  465.             }
  466.         }
  467.     }
  468.     else if (c == '$') {
  469.         p= ++pat;
  470.         while (isalnum(*p) || *p == '_')
  471.             ++p;
  472.         q= getenv(makestr(pat, p));
  473.         if (q != NULL)
  474.             buf= addstr(buf, q, end);
  475.         pat= p;
  476.     }
  477.     else if (c == QUOTE && (pat[1] == '$' || pat[1] == '~'))
  478.         ++pat;
  479.     
  480.     while (buf < end && (c= *pat++) != EOS) {
  481.         switch (c) {
  482.         
  483.         case QUOTE:
  484.             if ((c= *pat++) != EOS && index("\\*?[", c) != NULL)
  485.                 *buf++ = c;
  486.             else {
  487.                 *buf++ = QUOTE;
  488.                 --pat;
  489.             }
  490.             break;
  491.         
  492.         case '*':
  493.             *buf++ = M_ALL;
  494.             break;
  495.         
  496.         case '?':
  497.             *buf++ = M_ONE;
  498.             break;
  499.         
  500.         case '[':
  501.             if (*pat == EOS || index(pat+1, ']') == NULL) {
  502.                 *buf++ = c;
  503.                 break;
  504.             }
  505.             *buf++ = M_SET;
  506.             c= *pat++;
  507.             do {
  508.                 *buf++ = c;
  509.                 if (*pat == '-' && (c= pat[1]) != ']') {
  510.                     *buf++ = M_RNG;
  511.                     *buf++= c;
  512.                     pat += 2;
  513.                 }
  514.             } while ((c= *pat++) != ']');
  515.             *buf++ = M_END;
  516.             break;
  517.         
  518.         default:
  519.             *buf++ = c;
  520.             break;
  521.  
  522.         }
  523.     }
  524.     *buf= EOS;
  525.     
  526.     glob1(start, &files);
  527.     
  528.     if (files.len == 0) {
  529.         /* Change meta characters back to printing characters */
  530.         for (buf= start; *buf != EOS; ++buf) {
  531.             if (*buf & 0200)
  532.                 *buf &= ~0200;
  533.         }
  534.         return 0; /* No match */
  535.     }
  536.     else {
  537.         int i, len;
  538.         
  539.         qsort((char*)files.item, (size_t)files.len, (size_t)sizeof(char*), compare);
  540.         buf= start;
  541.         *buf= EOS;
  542.         for (i= 0; i < files.len; ++i) {
  543.             len= (int)strlen(files.item[i]);
  544.             if (len+1 > size)
  545.                 break;
  546.             strcpy(buf, files.item[i]);
  547.             buf += len+1;
  548.             size -= len+1;
  549.         }
  550.         discard(&files);
  551.         return i;
  552.     }
  553. }
  554.  
  555. #ifdef MAIN
  556. /*
  557.  * Main program to test 'glob' routine.
  558.  */
  559.  
  560. main(argc, argv)
  561.     int argc;
  562.     char **argv;
  563. {
  564.     int i, j, n;
  565.     char *p;
  566.     char buffer[10000];
  567.  
  568.     if (argc < 2) {
  569.         fprintf(stderr, "usage: %s pattern ...\n", argv[0]);
  570.         exit(2);
  571.     }
  572.     for (i= 1; i < argc; ++i) {
  573.         printf("%s: ", argv[i]);
  574.         n= glob(argv[i], buffer, (unsigned int)(sizeof buffer));
  575.         printf("%d\n", n);
  576.         p= buffer;
  577.         if (n == 0)
  578.             ++n;
  579.         for (j= 0; j < n; ++j) {
  580.             printf("\t%s\n", p);
  581.             p += strlen(p) + 1;
  582.         }
  583.     }
  584.     exit(0);
  585. }
  586. #endif
  587.